import java.util.*;
public class TestDemo2B {
    public int FindGreatestSumOfSubArray(int[] array){
        int []dp=new int [array.length];
        dp[0]=array[0];
        int maxValue=array[0];//防止只有一个数的情况
        for(int i=1;i<array.length;i++){
            dp[i]=Math.max(dp[i-1]+array[i],array[i]);//更新最大值
            if(dp[i]>maxValue){
                maxValue=dp[i];//存放最大值
            }
        }
        return maxValue;
    }
    public int FindGreatestSumOfSubArray1(int []array){
        int total=array[0];
        int maxValue=array[0];
        //for循环,用来检查i下标下的连续子序列的和
        for(int i=1;i<array.length;i++){
            //如果之前total累计的和>0,说明当前的数据+tota,有利于增大
            if(total>0) {
                total += array[i];
            }
            //如果之前累计的和<0,不利于整体增大,丢失之前的所有数据
            else{
                total=array[i];
            }
            if(total>maxValue){//每次记录加了数据的和
                maxValue=total;
            }
        }
        return maxValue;
    }
    //输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。(Topk问题)
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k){
        ArrayList<Integer>list=new ArrayList<>();
        if(input==null||k<=0||input.length<k){
            return list;
        }//建立大根堆(堆顶为最大值)
        PriorityQueue<Integer>queue=new PriorityQueue<>(k,Collections.reverseOrder());
        for(int i=0;i<input.length;i++){
            if(queue.size()<k){
                queue.offer(input[i]);//先提前插入k个数据,queue会自动进行排序
            }else{//如果小于队堆元素就需要淘汰堆顶元素并且插入当前下标元素
                if(queue.peek()>input[i]){
                    queue.poll();
                    queue.offer(input[i]);
                }
            }
        }//把前k个最小元素放入list中
        while(queue.size()>0){
            list.add(queue.poll());
        }
        return list;
    }

    //数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组
    //{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
    public static int MoreThanHalfNum_Solution(int [] array){
        if(array==null||array.length==0){
            return 0;
        }
        Map<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){//判断当前下标值是否是第一次出现
                int count=map.get(array[i]);
                count++;
                map.put(array[i],count);
            }else{
                map.put(array[i],1);
            }
            if(map.get(array[i])>array.length/2){
                return array[i];
        }
        }
        return 0;
    }
    public static void main3(String[] args) {
        int[]array={1,2,3,2,2,2,5,4,2};
        System.out.println(MoreThanHalfNum_Solution(array));
    }
    public int MoreThanHalfNum_Solution1(int[]array ){
        if(array==null||array.length==0){
            return 0;
        }
        int target=array[0];
        int times=1;
        for(int i=0;i<array.length;i++){
            if(times==0){
                target=array[i];
                times=1;
            }
            if(target==array[i]){
                times++;
            }else{
                times--;
            }
        }int count=0;
        for(int i=0;i<array.length;i++){
            if(target==array[i]){
                count++;
            }
        }
        return count>array.length/2?target:0;
    }
    public int MoreThanHalfNum_Solution3(int[]array ){
        //超过数组一半长度的元素的值肯定在数组的中间长度内
        if(array==null){
            return 0;
        }
        Arrays.sort(array);//排序
        //不减一的目的是为了要取超过数组一半的元素的下标
        int target=array[array.length/2];
        int count=0;
        for(int i=0;i<array.length;i++){
            if(target==array[i]){
                count++;
            }
        }
        return count>array.length/2?target:0;
    }
//请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字
//符串为We%20Are%20Happy。
    public String replaceSpace(StringBuffer str){
        int count=0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' '){
                count++;
            }
        }
        int new_length=str.length()+2*count;
        int old_end=str.length()-1;
        int new_end=new_length-1;
        while(old_end>=0&&new_end>=0){
            if(str.charAt(old_end)==' '){
                str.setCharAt(new_end--,'0');
                str.setCharAt(new_end--,'2');
                str.setCharAt(new_end--,'%');
            }else{
                str.setCharAt(new_end--,str.charAt(old_end--));
            }
        }
        return str.toString();
    }

    //给定一个仅由小写字母组成的字符串。现在请找出一个位置，删掉那个字母之后，字符串变成回文。请放心总会有一
    //个合法的解。如果给定的字符串已经是一个回文串，那么输出-1。
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        int []start=new int [1];//记录左边不回文元素的下标
        int []end=new int[1];//记录右边不回文元素的下标
        while(num>0){
            StringBuffer sb=new StringBuffer(sc.next());
            if(IsPalindrome(sb,start,end)){//代表字符已经回文了
                System.out.println("-1");
            }else{//不回文的时候
                sb.deleteCharAt(end[0]);//先删除右边不回文元素的值
                if(IsPalindrome(sb,null,null)){
                    System.out.println(end[0]);
                }else{//左边不回文元素的下标
                    System.out.println(start[0]);
                }
            }
            num--;
        }
    }
    public static boolean IsPalindrome(StringBuffer sb,int []start,int []end){
        int left=0;
        int right=sb.length()-1;
        boolean result=true;
        while(left<=right){
            if(sb.charAt(left)==sb.charAt(right)){
                left++;
                right--;
            }else{//左右字符不相等直接返回
                result=false;
                break;
            }
        }
        if(start!=null){//记录左边不回文元素的下标
            start[0]=right;
        }
        if(end!=null){//记录右边不回文元素的下标
            end[0]=left;
        }
        return result;
    }


    public String PrintMinNumber(int [] numbers) {
        if(numbers == null){
            return new String();
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int e : numbers){
            list.add(e);
        }
        Collections.sort(list, new Comparator<Integer>(){
            @Override
            public int compare(Integer x, Integer y){
                String xs = x + "" + y;
                String ys = y + "" + x;
                return xs.compareTo(ys);
            }
        });
        String result = new String();
        for(Integer e : list){
            result += e;
        }
        return result;
    }
            }


